package com.yonyouup.ucostcontrol.expression;
import java.util.*;


/**
 * 表达式 实例类
 * @author wangzhuo
 */
public class Expression {
	//原始的 token list 中缀表达式
	private ArrayList<String> tokens = null;
	//Reverse Polish
	private ArrayList<String> reversePolishTokens = null;
	
	//原始表达式
	private String expression = null;
	//表达式上下文
	private Map<String, Object> context = null;
	//运算符优先级map
	private static Map<String, Integer> operatorMap = null;
	//运算符delim
	private static String delims = "+-*/()&|!=><?:";
	
	//可以右联= 作为两个字符的运算符的 字符集合
	private static Set<String> leftOperatorsSet = null;
	
	static {
		operatorMap = new HashMap<String, Integer>();
		operatorMap.put("+", 4);
		operatorMap.put("-", 4);
		operatorMap.put("*", 3);
		operatorMap.put("/", 3);
		operatorMap.put("(", 1);
		operatorMap.put(")", 1);
		operatorMap.put("!", 2);
		operatorMap.put("&", 11);
		operatorMap.put("|", 12);
		operatorMap.put("==", 7);
		operatorMap.put("!=", 7);
		operatorMap.put(">", 6);
		operatorMap.put(">=", 6);
		operatorMap.put("<", 6);
		operatorMap.put("<=", 6);
		
		operatorMap.put("?:", 13);
		operatorMap.put("?", 13);
		operatorMap.put(":", 13);
		
		
		leftOperatorsSet = new HashSet<>();
		leftOperatorsSet.add("=");
		leftOperatorsSet.add("!");
		leftOperatorsSet.add(">");
		leftOperatorsSet.add("<");
	}
	
	/**
	 * @param expression 表达式字符串
	 */
	public   Expression(String expression) {
		this.expression = expression.replace(" ", "");
		this.tokens = tokenize(this.expression);
		this.reversePolishTokens = generateReversePolish(this.tokens);
	}
	
	public String toReversePolish() {
		String res = "";
		for (String token : reversePolishTokens) {
			res += token + ",";
		}
		return res;
	}
	
	/**
	 * 分词
	 * @param expression 表达式
	 * @return token list
	 */
	private ArrayList<String> tokenize(String expression){
		StringTokenizer stringTokenizer = new StringTokenizer(expression,delims,true);
		ArrayList<String> tokens = new ArrayList<String>();
        String previewToken = null;
		// 将表达式分词， 注意合并两个字符的运算符
        while (stringTokenizer.hasMoreElements()) {   
        	String currToken = stringTokenizer.nextToken();
			if (isCombinable(previewToken, currToken)){
				//移除最后一个 
				tokens.remove(tokens.size()-1);
				String newToken = previewToken + currToken;
				tokens.add(newToken);
				previewToken = newToken;
			}
			else{
				tokens.add(currToken);
				previewToken = currToken;
			}
        }
        return tokens;
	}
	
	/**
	 * 判断两个运算符是否可联合
	 * @param leftToken
	 * @param rightToken
	 * @return ture or false
	 */
	private boolean isCombinable(String leftToken, String rightToken){
		if ("=".equals(rightToken)){
			if (leftOperatorsSet.contains(leftToken)){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * @param expression 表达式字符串
	 * @param context 表达式的上下文
	 */
	public   Expression(String expression, Map<String, Object> context)  {
		this(expression);
		this.context = context;
	}
	
	/**
	 * 生成逆波兰表达式
	 * @param 中缀表达式  例如: (1+2) < 3 , 1==1 ? 2 : 3
	 * @return 逆波兰表达式，后缀表达式 , 例如： 1 2 + 3 < , 
	 */
	private ArrayList<String> generateReversePolish(ArrayList<String> tokens) throws ExpressionException{
		//运算符stack， 和 操作数stack
		Stack<String> operatorStack = new Stack<>();
		Stack<String> numberStack = new Stack<>();
		for (String token : tokens) {
			//如果是操作数，直接插入到操作数stack
			if (!operatorMap.containsKey(token)){
				numberStack.push(token);
			}
			//如果是运算符，则与运算符栈顶的 运算符比较优先级，如果大于等于栈顶运算符，则插入栈顶， 否则，则取出栈顶元素放入操作数栈，再将其放入运算符栈
			//如果是）运算符，则取出运算符栈中的token 直到碰到 （ , 都放入 操作数栈
			else{
				if (operatorStack.empty()){
					operatorStack.push(token);
				}
				else{
					//如果是右括号 则要找到左括号 并且一次入栈到 操作数栈
					if (token.equals(")")){
						String popToken = null;
						try {
							while( !(popToken = operatorStack.pop()).equals("(") ){
								numberStack.push(popToken);
							}
							continue;
						} catch (EmptyStackException e) {
							throw new ExpressionException("invalid expression:  '" + this.expression +"' , 表达式错误，缺少'('。", e);
						}
					}
					//如果是:, 则要找到? 并且一次入栈到 操作数栈
					if (token.equals(":")){
						String popToken = null;
						try {
							while( !(popToken = operatorStack.pop()).equals("?") ){
								numberStack.push(popToken);
							}
							operatorStack.push("?:");
							continue;
						} catch (EmptyStackException e) {
							throw new ExpressionException("invalid expression:  '" + this.expression +"' , 表达式错误，三目运算符缺少'?'。", e);
						}
					}
					
					String preOperator = operatorStack.peek();
					//如果之前的操作符是（ ，则不用比较优先级 当前操作符直接入栈
					if (preOperator.equals("(")){
						operatorStack.push(token);
					}
					//比较操作符优先级， 如果该操作符优先级大于等于 ， 则直接入栈
					else if (operatorMap.get(token) <= operatorMap.get(preOperator)){
						operatorStack.push(token);
					}
					//如果该操作符优先级 小于， 则在将该操作符如栈之前 要把栈顶操作符 弹出 插入 操作数栈
					else{
						numberStack.push( operatorStack.pop());
						operatorStack.push(token);
					}
					
				}
				
			}
		}
		
		while (!operatorStack.empty()) {
			numberStack.push( operatorStack.pop());
		} 
		ArrayList<String> resArrayList = new ArrayList<>();
		String[] array = numberStack.toArray(new String[]{});
		for (int i = 0; i < array.length; i++) {
			resArrayList.add(array[i]);
		}
		
		return resArrayList;
	}
	
	
	
	/**
	 * 计算表达式
	 * @return
	 * @throws ExpressionException
	 */
	public Object calculate() throws ExpressionException {
		Stack<String> stack = new Stack<String>();
		for (String token : this.reversePolishTokens) {
			//如果是操作数则入栈
			if (!operatorMap.containsKey(token)){
				stack.push(token);
			}
			else{
				try {
					//一元运算符
					if (token.equals("!")){
						Object v = getValueFromContext(stack.pop(), this.context);
						stack.push(CalculatorHelper.calculate(v, token).toString());
					}
					//三元运算符
					else if (token.equals("?:")){
						
						Object val3 = getValueFromContext(stack.pop(), this.context);
						Object val2 = getValueFromContext(stack.pop(), this.context);
						Object val1 = getValueFromContext(stack.pop(), this.context);
						stack.push(CalculatorHelper.calculate(val1, val2,val3, token).toString());
					}
					//二元运算符
					else {
						Object right = getValueFromContext(stack.pop(), this.context);
						Object left = getValueFromContext(stack.pop(), this.context);
						stack.push(CalculatorHelper.calculate(left, right, token).toString());
					}
				} catch (EmptyStackException e) {
					throw new ExpressionException("invalid expression:  '" + this.expression +"'", e);
				}
				
			}
		}
		if (stack.size() == 1){
			String valueString = stack.pop();
			return getValueFromContext(valueString, new HashMap<String, Object>());
		}
		else{
			throw new ExpressionException("invalid expression:  '" + this.expression +"'" , null);
		}
		
	}
	
	
	private Object getValueFromContext(String variable, Map<String, Object> context){
		//判断变量是否 是常量
		Double num = null;
		Boolean bool = null;
		try {
			num = Double.parseDouble(variable);
			return num;
		} catch (NumberFormatException e) {}
		if (num == null){
			if (variable.equalsIgnoreCase("true") || variable.equalsIgnoreCase("false")){
				bool = Boolean.parseBoolean(variable);
				return bool;
			}
		}
		
		
		//变量从 上下文中去寻找值
		if (context != null && context.containsKey(variable)){
			return context.get(variable);
		}
		throw new ExpressionException("invalid expression:  '" + this.expression + "' ; " + variable + " undefined!", null);
	}
	
	
}

